package com.future;

import com.future.util.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * Description: 235. 二叉搜索树的最近公共祖先
 *
 * @author weiruibai.vendor
 * Date: 2023/1/3 09:30
 */
public class Solution_235 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> childParent = new HashMap<>();
        childParent.put(root, null);
        buildChildParent(root, childParent);
        List<TreeNode> list = new ArrayList<>();
        while (p != null) {
            list.add(p);
            p = childParent.get(p);
        }
        while (!list.contains(q)) {
            q = childParent.get(q);
        }
        return q;
    }

    private void buildChildParent(TreeNode root, Map<TreeNode, TreeNode> childParent) {
        if (root == null) {
            return;
        }
        childParent.put(root.left, root);
        buildChildParent(root.left, childParent);
        childParent.put(root.right, root);
        buildChildParent(root.right, childParent);
    }

    public TreeNode lowestCommonAncestor_v2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> path_p = getPath(root, p);
        Stack<TreeNode> path_q = getPath(root, q);
        while (!path_q.empty()) {
            TreeNode pop = path_q.pop();
            if (path_p.contains(pop)) {
                return pop;
            }
        }
        return root;
    }

    public Stack<TreeNode> getPath(TreeNode root, TreeNode target) {
        Stack<TreeNode> path = new Stack<>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }

}
